package dp;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:交错字符串，也称为交叉字符串，是一种字符串处理问题。给定三个字符串：s1、s2和s3，
 * 判断s3是否可以通过将s1和s2中的字符交错而成，且保持相对顺序不变。
 * author: Mr.Du
 * Date: 2023/4/13
 * Time: 11:29
 */
public class IsInterleave {

    public static void main(String[] args) {
        System.out.println(isInterleave("abc","def","adbecf"));
    }

    /**
     * 可以定义一个二维布尔数组dp，其中dp[i][j]表示s1的前i个字符和s2的前j个字符能否交错排列形成s3的前i+j个字符。
     * 可以通过以下状态转移方程来填充dp数组：
     * @param s1
     * @param s2
     * @param s3
     * @return
     */
    public static boolean isInterleave(String s1, String s2, String s3) {
        int len1 = s1.length();
        int len2 = s2.length();
        int len3 = s3.length();

        // 如果s1和s2的长度之和不等于s3的长度，则s3不能是s1和s2的交错字符串
        if (len1 + len2 != len3) {
            return false;
        }

        // 创建一个二维布尔数组，用于记录状态
        boolean[][] dp = new boolean[len1 + 1][len2 + 1];

        // 初始化dp数组
        dp[0][0] = true;

        // 初始化第一列，表示s1为空字符串时，s3是否能够通过s2形成交错字符串
        for (int i = 1; i <= len2; i++) {
            dp[0][i] = dp[0][i - 1] && s2.charAt(i - 1) == s3.charAt(i - 1);
        }

        // 初始化第一行，表示s2为空字符串时，s3是否能够通过s1形成交错字符串
        for (int i = 1; i <= len1; i++) {
            dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
        }

        // 填充dp数组
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1))
                        || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
            }
        }

        // 返回dp数组的最后一个元素，表示s3是否是s1和s2的交错字符串
        return dp[len1][len2];
    }
}
